/**
 * 最小的 K 个数
 *
 *  描述
 * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是
 * 4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 *
 * 数据范围：
 * 0≤k,n≤10000，数组中每个数的大小
 * 0≤val≤1000
 *
 * 要求：
 * 空间复杂度 O(n) ，
 * 时间复杂度 O(nlogk)
 */

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 使用大根堆, 这就是对 topk 算法 使用的方法
 * 我们将每位数加入 堆中, 但是一直维持堆中元素
 * 在 k 个, 然后我们要是要取小的前 k 个数的话
 * 那么我们就使用大根堆, 这样保证堆中 k 个元素
 * 每次出的都是比这 k 个元素大的元素, 那么最后
 * 面剩下来的就是最小的前 k 个元素了.
 * 反之, 要是要我们求最大的前 k 个元素, 也是使用
 * 这个方法, 但是使用的是小根堆
 * 时间复杂度 : O(n log k)
 * 空间复杂度 : O(k)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {

        // 创建大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        int n = input.length;

        for (int i = 0; i < n; i++) {

            queue.add(input[i]);

            // 保持 队列中有 k 个元素
            if (queue.size() > k) {

                // 要是超过了 限制, 出掉最大的元素
                queue.poll();
            }
        }

        // 返回结果
        return new ArrayList<>(queue);
    }
}